package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code93LongestPalindromicSubstring {

    public String longestPalindrome(String s) {
        char[] str = manacher(s);
        int r = -1;
        int c = -1;
        int[] pArr = new int[str.length];
        // 记录最大长度和中心坐标
        int[] max = new int[2];
        for (int i = 0; i < str.length; i++) {
            pArr[i] = i <= r ? Math.min(r - i + 1, pArr[2 * c - i]) : 1;
            // 尝试扩
            while (i - pArr[i] >= 0 && i + pArr[i] < str.length) {
                if (str[i - pArr[i]] == str[i + pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            // 新的最大值
            if (i + pArr[i] - 1 > r) {
                r = i + pArr[i] - 1;
                c = i;
            }
            if (pArr[i] > max[1]) {
                max[0] = i;
                max[1] = pArr[i];
            }
        }
        return new String(str, max[0] - max[1] + 1, 2 * max[1] - 1).replace("#", "");
    }


    /**
     * abc => #a#b#c#
     *
     * @param s
     * @return
     */
    public char[] manacher(String s) {
        int n = s.length();
        char[] str = new char[n * 2 + 1];
        for (int i = 0; i < str.length; i++) {
            str[i] = (i & 1) == 0 ? '#' : s.charAt(i / 2);
        }
        return str;
    }
}
